//
//  String.swift
//  JNLeetCode
//
//  Created by Renju Jiang on 2018/12/8.
//  Copyright © 2018 jiangrenju. All rights reserved.
//

import Foundation

class LeetCodeString {
    
    //abcabcbb
    func lengthOfLongestSubstring(_ s: String) -> Int {
        
        var hashMap: [String: Int] = [:]
        var left = 0
        var maxLength = 0
        
        for i in 0..<s.count {
            let char = s[s.index(s.startIndex, offsetBy: i)]
            let str = String(char)
            left = max(hashMap[str] ?? 0, left)
            hashMap[str] = i + 1
            maxLength = max(maxLength, i - left + 1)
        }
        
        return maxLength
    }
    
    func longestCommonPrefix(strs: [String]) -> String {
        
        guard let firstStr = strs.first else { return "" }
        var commonString = ""
        
        for i in 0..<firstStr.count {
            let char = firstStr[firstStr.index(firstStr.startIndex, offsetBy: i)]
            
            var common = true
            for j in 1..<strs.count {
                
                let perStr = strs[j]
                guard i < perStr.count else {
                    common = false
                    break
                }
                if perStr[perStr.index(perStr.startIndex, offsetBy: i)] != char {
                    common = false
                    break
                }
            }
            
            if common {
                commonString.append(char)
            } else {
                break
            }
        }
        
        return commonString
    }
    
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        
        if s1.count > s2.count {
            return false
        }
        
        var hashMap: [String: Int] = [:]
        var const = s1.count, length1 = s1.count, left = 0

        for i in 0..<s1.count {
            let char = s1[s1.index(s1.startIndex, offsetBy: i)]
            let str = String(char)
            if let count = hashMap[str] {
                hashMap[str] = count + 1
            } else {
                hashMap[str] = 1
            }
        }
        
        for right in 0..<s2.count {
            let char = s2[s2.index(s2.startIndex, offsetBy: right)]
            let str = String(char)
            
            let count = hashMap[str] ?? 0
            hashMap[str] = count - 1
            if count > 0 {
                const -= 1
            }
            
            while const == 0 {
                if right - left + 1 == length1 {
                    return true
                }
                
                let leftStr = String(s2[s2.index(s2.startIndex, offsetBy: left)])
                let leftCount = (hashMap[leftStr] ?? 0) + 1
                if leftCount > 0 {
                    const += 1
                }
                hashMap[leftStr] = leftCount
                left += 1
            }
        }
        return false
    }
    
    func multipy(_ s1: String, _ s2: String) -> String {
        
        if Int(s1) == 0 || Int(s2) == 0 {
            return "0"
        }
        
        var nums: [Int] = [Int].init(repeating: 0, count: s1.count + s2.count)
        var carry = 0, product = 0
        var jIndex = s2.count - 1
        
        for i in (0..<s1.count).reversed() {
            
            jIndex = s2.count-1
            carry = 0
            
            let char1 = s1[s1.index(s1.startIndex, offsetBy: i)]
            let num1 = Int(String(char1)) ?? 0
            
            for j in (0..<s2.count).reversed() {
                jIndex -= 1

                let char2 = s2[s2.index(s2.startIndex, offsetBy: j)]
                let num2 = Int(String(char2)) ?? 0

                product = num1 * num2 + carry + nums[i+j+1]
                
                carry = product / 10
                
                nums[i+j+1] = product % 10
                
            }
            nums[i+jIndex+1] = carry
        }
        
        var result = ""
        nums.forEach { (num) in
            if result.isEmpty {
                if num > 0 {
                    result.append(String(num))
                }
            } else {
                result.append(String(num))
            }
        }
        
        return result
    }
    
    func reverseWords() {
        //pass
    }
    
    func simplifyPath(_ path: String) -> String {
        
        var list: [String] = []
        let arr = path.split(separator: "/")
        for sub in arr {
            if sub == "." {
                continue
            } else if sub == ".." {
                if !list.isEmpty {
                    list.removeLast()
                }
            } else {
                list.append(String(sub))
            }
        }
        
        var result = String()
        list.forEach { (s) in
            result.append("/\(s)")
        }
        
        if result.isEmpty {
            result = "/"
        }
        
        return result
    }

    func restoreIPAddresses(_ s: String) -> [String] {
        var result: [String] = []
        let ips: String = ""
        restoreIPAddresses(s: s, k: 4, ips: ips, result: &result)
        return result
    }
    
    private func restoreIPAddresses(s: String, k: Int, ips: String, result: inout [String]) {
        if k == 0 {
            if s.count == 0 {
                result.append(ips)
            }
        } else {
            for i in 1...3 {
                if s.count < i {
                    break
                }
                
                let str = String(s[s.startIndex..<s.index(s.startIndex, offsetBy: i)])
                
                let isValid: Bool = {
                    if str.isEmpty || str.count > 3 || (str.count > 1 && str.hasPrefix("0")) {
                        return false
                    }
                    if let num = Int(str) {
                        if num < 0 || num > 255 {
                            return false
                        }
                    } else {
                        return false
                    }
                    return true
                }()
                
                if isValid {
                    var ss = "\(ips)\(str)"
                    if k != 1 {
                        ss.append(".")
                    }
                    restoreIPAddresses(s: String(s[s.index(s.startIndex, offsetBy: i)..<s.endIndex]), k: k-1, ips: ss, result: &result)
                }
            }

        }

    }
    
    private func isValid(_ s: String?) -> Bool {
        guard let str = s else { return false }
        
        if str.count > 0 && str.hasPrefix("0") {
            return false
        }
        
        if let num = Int(str) {
            if num < 0 || num > 255 {
                return false
            }
        } else {
            return false
        }
        
        return true
    }
    
    
}
